#!/usr/bin/python  
#Authors:
#Daniel Pflieger
#Brian Groelinger
#Emma Murray
'''
Traveling Salesman Problem (TSP): given a complete graph of n cities, find the shortest path that creates
a non-connected sub-graph.  This implementation uses a greedy algorithm, which does compromise accuracy,
in order to meet speed requirements. NOTE: the greedy algorithm will not work for a modified version of the
TSP in which the initial graph is incomplete.  

We begin by creating an array of the distances between n cities (these are the edges of the graph). The
algorithm begins with the first city in the distances array (which is also the first city in the cities array).
The algorithm loops through the distances array searching for the lowest cost edge that begins in the current
city and has NOT already been visited. It adds this edge to the tour array. The algorithm will loop until it
has n-1 edges listed in the tour.
'''

# import standard Python libraries.
# negelecting to import the vital files may cause bruising to the head.
import math
import sys
import time
import numpy as np

MAX_DIST_ON_EARTH = 12600

# cities = [[cid,x,y], [cid,x,y]....]
# imagine a 2-D graph.  These are the x-coord and the y-coords with a city ID
cities = []

# distances = [[cid1, cid2,] dist] ... ]
distances=[]

# we find the greedy algorithim then store the best fit to this list
tour = []

# FUNCTION: calculates the rounded Euclidean distance between c1 and c2
# sqrt[(x2 - x1)^2 + (y2 - y1)^2]
def distance(x1,y1, x2, y2):
      xdis = (x2 - x1)**2
      ydis = (y2 - y1)**2
      dist = math.sqrt(xdis+ydis)
      dist = round(dist)
      return dist

# command line selection of input file
# dont forget to enter a file name! Stupid in = stupid out.
if len(sys.argv) != 2:
      sys.exit("Please provide the input file name")
     
# handling the input/output files
infile = sys.argv[1]  
outfile = infile + ".tour"
   
print 'Input file is :', infile
print 'Output file is :', outfile
   
   
# open file with read only permission
input = open(infile, 'r')

# is the file empty?
city = input.readline()

# count the num of cities we have.
count = 0

# while there is still info in the file create an array that has all cities and
# their positions.  We need this info to calucalte the city distances.
while city:
   #parse each line into list
   #split line by white space
   temp = city.split()
   #convert string to int
   temp2 = [int(i) for i in temp]
   #move into cities list
   cities.append(temp2)
   #move to next line
   city = input.readline()  
   count = count + 1
#close input file
input.close()

# we iterate through all the cities and get the distances between each city.
# all edges except city(k) to city(k) edges must be calculated; tour can
# feasibly use an edge going from a to be OR b to a.
for i in range (len(cities)):
        for j in range ((len(cities))):
                if i !=  j:
                        city1 = cities[i][0]
                        c1x = cities[i][1]
                        c1y = cities[i][2]
                        city2 = cities[j][0]
                        c2x = cities[j][1]
                        c2y = cities[j][2]
                        dist = distance(c1x,c1y,c2x,c2y)
                        tmp3 = [city1, city2, dist]
                        distances.append(tmp3)
output = open(outfile, 'w')
#output.write(str(count) + '\n')
print 'the number of cities is ' + str(count)

i = 0
tour = []
visCity = []                            # holds the visited vertices for comparisons
curCity = distances[0][0]               # assign first city in distances as starting point
totalDist = 0


while (len(tour) < (len(cities)-1)):    # tour is complete when it holds n-1 EDGES
        lowEdge = [-1,-1,sys.maxint]    # for each starting city initialize lowEdge with max integer value
        for x in range(len(distances)):
            nextEdge = distances[x]
            if curCity == nextEdge[0] and nextEdge[1] not in visCity:
                if nextEdge[2] < lowEdge[2]:
                        lowEdge = nextEdge      
        tour.append(str(lowEdge[0]))#dp changed the function so we only have a list of cities.  This list is the starting city
        visCity.append(curCity)
        curCity = lowEdge[1]            # next starting city is v2 in the lowest edge of current round
        totalDist = totalDist + lowEdge[2] #dp added the line to sum distances
tour.append(str(lowEdge[1])+ '\n')

totalDist = int(totalDist)
output.write(str(totalDist) + '\n')
print 'cities'
print cities
print 'tour'
print type(tour)
tour =  ("\n".join(tour))
print tour
print 'Total Distance'
print totalDist
output.write(tour)
